﻿#include <iostream>

typedef char TElemType;
TElemType Nil = '#';
#define MaxTreeSize 3

typedef struct BiTNode {
    TElemType data;
    struct BiTNode *lchild, *rchild;
} BiTNode, *BiTree;


void InitBiTree(BiTree &BT) {
    BT = NULL;
}

void CreatBiTree(BiTree &BT) {
    TElemType e;
    std::cin >> e;
    if (e == Nil)
        BT = NULL;
    else {
        BT = (BiTNode *) malloc(sizeof(BiTNode));
        if (!BT) exit(-1); // 申请新结点失败
        BT->data = e;
        CreatBiTree(BT->lchild);  // 递归构造左子树
        CreatBiTree(BT->rchild);  // 递归构造右子树
    }
}

void Visit(BiTree BT) {
    printf("%c", BT->data);
}

int TreeDepth(BiTree BT) {
    int Lh, Rh;
    if (!BT)
        return 0;
    Lh = TreeDepth(BT->lchild);
    Rh = TreeDepth(BT->rchild);
    return Lh > Rh ? Lh + 1 : Rh + 1;
}

/*
 * 非递归算法求二叉树的高度
 * 操作步骤：采用层次遍历的算法，设置变量level记录当前结点所在的层数，设置变量last指向当前层的最右结点，每次层次遍历出队时与last指针比较，
 * 若两者相等，则层数加1，并让last指向下一层的最右结点，直到遍历完成。level的值即二叉树的高度。
 */
int NRTreeDepth(BiTree BT) {
    if (!BT) return 0;  // 空树，高度为0
    BiTNode *queue[MaxTreeSize];
    BiTNode *p;
    int front = -1, rear = -1;
    int last=0, level = 0;
    queue[++rear] = BT;// 根结点入队
    while (front != rear) {
        p = queue[++front];// 队头元素出队，并复制给p
        if (p->lchild) {
            queue[++rear] = p->lchild;
        }
        if (p->rchild) {
            queue[++rear] = p->rchild;
        }
        if (front == last) {
            level++;
            last = rear;
        }
    }
    return level;
}


int main() {
    BiTree BT;
    InitBiTree(BT);
    printf("创建一棵二叉树,请按照前序序列输入树中的结点（'#'表示子树为空）：\n");
    CreatBiTree(BT);

    printf("使用递归算法，树的高度为：");
    printf("%d\n", TreeDepth(BT));

    printf("使用非递归算法，树的高度为：");
    printf("%d\n", NRTreeDepth(BT));

    return 0;
}